package main

// 763. 划分字母区间
func main() {
	str := "ababcbacadefegdehijhklij"
	partitionLabels(str)
}

func partitionLabels(s string) []int { // 贪心算法，一个维护字母存在的情况，一个维护当前所有字母是否已经包含的情况
	strMap := make(map[int32]int)
	var res []int
	currMap := make(map[int32]int)

	for _, i := range s {
		strMap[i]++
	}

	currLen := 0
	for _, i := range s {
		currMap[i] = 0
		currLen++
		strMap[i] = strMap[i] - 1
		if strMap[i] == 0 { // 如果当前这个清空了，那可以从当前Set移除
			delete(currMap, i)
		}

		if len(currMap) == 0 { // 如果Set清空了，那可以从下一个开始
			res = append(res, currLen)
			currLen = 0
		}
	}

	return res
}

// 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
//
//注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
//
//返回一个表示每个字符串片段的长度的列表。
//
//
//
//示例 1：
//输入：s = "ababcbacadefegdehijhklij"
//输出：[9,7,8]
//解释：
//划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
//每个字母最多出现在一个片段中。
//像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
//示例 2：
//
//输入：s = "eccbbbbdec"
//输出：[10]
//
//
//提示：
//
//1 <= s.length <= 500
//s 仅由小写英文字母组成
